Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Звіт до лабораторної роботи № 3
На тему:
“Алгоритм шифрування з відкритим ключем RSA”
Варіант №16
Мета роботи: вивчити принцип функціонування асиметричних криптосистем з відкритими ключами на прикладі RSA, дослідити числові алгоритми, що використовуються у криптографії та реалізувати алгоритмічною мовою С++ алгоритм шифрування RSA.
Завдання
На основі інструментарію Visual C++ 2005 розробити Windows Forms програму CLR для реалізації вказаного проекту алгоритму криптографічної системи з відкритими ключами RSA.
Усі окремі алгоритми (наприклад, обчислення НСД бінарним алго ритмом Евкліда) реалізувати у вигляді підпрограм (функцій).
З метою компактності у завданні вказуються лише номери алгоритмів, на основі яких потрібно реалізувати загальний проект програ ми RSA. Розшифрування номерів подаються тут:
1. Алгоритм піднесення до степеню: 1.1. Метод справа-наліво двійкового потенціювання; 1.2. Метод зліва-направо двійкового потенціювання; 1.3. Рекурсивний метод двійкового потенцію вання; 1.4. Метод вікна; 1.5. Метод змінного вікна.
2. Обч. найбільшого спільного дільника: 2.1. Алгоритм Евклі да; 2.2. Бінарний алгоритм Евкліда.
3. Обч. оберненого значення за модулем: 3.1. Розширений ал горитм Евкліда; 3.2. Розширений бінарний алгоритм Евкліда.
4. Тести визначення простоти числа: 4.1. Тест Рабіна-Мілера; 4.2. Тест Соловея-Штрасена; 4.3. Тест Лемана.
=
Алг: 1.2; 2.1; 3.1; 4.1
Теоретичні відомості
Метод зліва-направо двійкового потенціювання.
Цей метод схожий до попереднього, з тією лиш різницею, що пе ребір символів вказівника степеню він виконує, починаючи зі старшо го розряду. Якщо представити вказівник у двійковому вигляді
, , (2.11)
де – кількість розрядів , то загальний алгоритм виглядатиме так:
Мовою С++ цей алгоритм виглядає так:
// обчислення
//визначення к-сті розрядів числа x
worker = x; n_x = 1;
while (worker > 1)
{ worker = worker >> 1; n_x++; }
//маска з "1" для старшого розрдяду x
mask = 1;
mask = mask << (n_x-1);
m = 1;
while (mask)
{
m = (m*m) % n;
if (x & mask)
m = (m*a) % n;
mask = mask >> 1;
}
У цьому алгоритмі за кожен прохід циклу обробляється один біт степеню. При цьому кількість піднесень до квадрату рівна кількості розрядів числа , а загальна кількість добутків визначається кількістю його одиничних розрядів. Отже чим менша вага (кількість “1”) числа , тим алгоритм двійкового потенціювання працює швидше.
Алгоритм Евкліда.
В основі алгоритму лежить повторне ділення із залишком: обчислюємо залишок , потім і так далі, поки залишок на стане рівним нулю.
Загальний алгоритм Евкліда обчислення НСД (,) для
Мовою С++ цей алгоритм виглядає так:
// обчислення НСД (,)
while (a != 0)
{
temp = b %a;
b = a;
a = temp;
}
nsd = b;
Розширений алгоритм Евкліда.
Звичайний алгоритм Евкліда для знаходження НСД (,) зводився до послідовного ділення із залишком
, , (2.30)
де , , НСД (,).
Якщо для послідовності (2.30) провести ряд перетворень та виразити усі залишки через та , тоді
,
,
,
,
(2.31)
Таким чином, ми отримали рекурентну формулу (2.31) для зна ходження НСД (,) у вигляді лінійної комбінації чисел та з цілими числами та . Якщо числа та взаємно прості, тоді НСД (,) = 1, і відповідно
1 = НСД (,) =. (2.32)
З формули (2.32) випливає, що обернене значення .
Загальний розширений алгоритм Евкліда
обчислення оберненого значення
Мовою С++ цей алгоритм виглядає так:
// обчислення
// вхід: числа a та n, для яких треба знайти nsd= НСД (,)
long long n1, c, k, nsd, c1, c2, k1, k2, q, r;
n1 = n; //резервуємо значення n
c2 = 1; c1 = 0; k2 = 0; k1 = 1;
while(n != 0)
{
q = a/n; r = a - q*n; c = c2 - q*c1; k = k2 - q*k1;
a = n; n = r; c2 = c1; c1 = c; k2 = k1; k1 = k;
}
nsd = a; c = c2; k = k2;
// якщо аглоритм дав від’ємне значення с, тоді с = с (mod n)
if (c < 0) c += n1;
// вихід: числа nsd, ...
